package com.medium;

import java.util.*;

/**
 * @authoer zsj
 * @date 2022/6/8 9:59
 */
public class alg {

    /**
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空。
     */
    public static boolean backspaceCompare(String s, String t) {
        return check(s).equals(check(t));
    }

    public static String check(String str) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '#') {
                if (ans.length() > 0) ans.deleteCharAt(ans.length() - 1);
            } else {
                ans.append(str.charAt(i));
            }
        }
        return ans.toString();
    }


    /**
     * 给定一个长度为 n 的整数数组height。有n条垂线，
     * 第 i 条线的两个端点是(i, 0)和(i, height[i])。
     * 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     * 说明：你不能倾斜容器。
     * <p>
     * bm破解  超时 过 54
     */
    public static int maxArea(int[] height) {
        int n = height.length;
        if (n == 2) {
            if (height[0] < height[1]) {
                return height[0];
            } else return height[1];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            //得到第一个端点
            int count = 0;
            for (int j = i + 1; j < n; j++) {
                //如果当前端点大于了开始端点
                if (height[j] > height[i]) {
                    count = Math.max(count, height[i] * (j - i));
                }
                //如果当前端点小于了起使端点
                if (height[j] <= height[i]) {
                    count = Math.max(count, height[j] * (j - i));
                }
            }
            ans = Math.max(count, ans);
        }
        return ans;
    }

    //双指针
    public static int maxArea2(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int ans = Math.min(height[l], height[r]) * (r - l);
        while (l < r) {
            //每次需要移动数字较小的那个
            ans = Math.max(Math.min(height[l], height[r]) * (r - l), ans);//得出当前结果
            if (height[l] < height[r]) {
                l++;
            } else r--;
        }
        return ans;
    }


    /**
     * 给定两个字符串s和 p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     * <p>
     * 滑动窗口思想
     * 如果
     */
    public List<Integer> findAnagrams(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        if (sl < pl) return new ArrayList<Integer>();
        List<Integer> ans = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pl; i++) {
            //得到p的词出现数量
            sCount[p.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        for (int i = 0; i < sl - pl; i++) {
            //剔除
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + pl) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    /**
     * 给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        //同样排除k为1的情况比如  [1,1,1] k=1
        if (k <= 1) {
            return 0;
        }
        int left = 0;
        int right = 0;
        //创建一个变量记录路上的乘积
        int mul = 1;
        //记录连续数组的组合个数
        int ans = 0;

        //用右指针遍历整个数组，每次循环右指针右移一次
        while (right < nums.length) {
            //记录乘积
            mul *= nums[right];
            //当大于等于k，左指针右移并把之前左指针的数除掉
            while (mul >= k) {
                mul /= nums[left];
                left++;
            }

            //每次右指针位移到一个新位置，应该加上 x 种数组组合：
            //  nums[right]
            //  nums[right-1], nums[right]
            //  nums[right-2], nums[right-1], nums[right]
            //  nums[left], ......, nums[right-2], nums[right-1], nums[right]
            //共有 right - left + 1 种
            ans += right - left + 1;

            //右指针右移
            right++;
        }
        return ans;
    }

    /**
     * 给定一个含有n个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，
     * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * <p>
     * 暴力解法1
     * 滑动数组
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            count = nums[i];
            if (count >= target) {
                ans = 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                count += nums[j];
                if (count >= target) {
                    ans = Math.min(j - i + 1, ans);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    public static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int start = 0;
        int end = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        while (end < n) {
            sum += nums[end];
            while (sum >= target) {
                //当前结果大于等于了target
                //记录
                ans = Math.min(ans, end - start + 1);
                //将start的值往后移一位
                start++;
                //将结果减去最前面的值直到sum的值不符合条件
                sum -= nums[start];
            }
            //一直往下加
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }


    /**
     * 你总共有n枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，
     * 其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
     * 给你一个数字n ，计算并返回可形成 完整阶梯行 的总行数。
     */
    public int arrangeCoins(int n) {
        int ans = 0;
        int need = 1;
        for (int i = 0; i < n; i++) {
            n -= need;
            need++;
            ans++;
            if (n < 0) {
                break;
            }
        }
        return ans;
    }

    /**
     * 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
     * 请你找到这个数组里第 k 个缺失的正整数。
     * <p>
     * 每个元素丢失的数量 =  当前元素 - 前一个元素 -1
     */
    public static int findKthPositive(int[] arr, int k) {
        for (int n : arr)
            if (n <= k) k++;
            else break; //else return k;
        return k;
    }


    /**
     * 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     */
    public static int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        //开始遍历并且标记
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private static void dfs(char[][] grid, boolean[][] visited, int n, int m) {
        if (n >= grid.length || n < 0 || m >= grid[0].length || m < 0
                || visited[n][m] || grid[n][m] == '0') {
            //设置结束条件，并且防止数组越界
            return;
        }
        visited[n][m] = true;
        dfs(grid, visited, n + 1, m);
        dfs(grid, visited, n - 1, m);
        dfs(grid, visited, n, m + 1);
        dfs(grid, visited, n, m - 1);
    }

    public static void main(String[] args) {

        char[][] arr = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}};
        int[][] arr2 = {{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}};
        findCircleNum(arr2);
    }

    /**
     * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
     * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
     * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
     * 返回矩阵中 省份 的数量。
     */
    public static int findCircleNum(int[][] isConnected) {
        int citys = isConnected.length;
        boolean[] visited = new boolean[citys];
        int ans = 0;
        for (int i = 0; i < citys; i++) {
            if (!visited[i]) {
                dfs2(isConnected, visited, i, citys);//当前是i城市
                ans++;
            }
        }
        return ans;
    }

    private static void dfs2(int[][] isConnected, boolean[] visited, int cur, int citys) {
        //关键在于如何往下拓展
        for (int index = 0; index < citys; index++) {
            if (isConnected[cur][index] == 1 && !visited[index]) {
                visited[cur] = true;//把相连的标记
                dfs2(isConnected, visited, index, citys);
            }
        }
    }


    /**
     * 给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
     * 注意： x 不必 是 nums 的中的元素。
     * 如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
     */
    public int specialArray(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (check2(nums,i))return i;
        }
        return -1;
    }

    private boolean check2(int[] nums, int i) {
        int res =0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j]>=i)res++;
        }
        return res==i;
    }

}
